#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <Stdbool.h>
//最小的k个数

void AdjustDown(int* a,int size,int root)
{
    int parent=root;
    int child=parent*2+1;
    while(child<size)
    {
        if(child+1<size&&a[child+1]>a[child])
            child++;
        if(a[parent]<a[child])
        {
            int tmp=a[child];
            a[child]=a[parent];
            a[parent]=tmp;
            parent=child;
            child=parent*2+1;
        }
        else
        {
            break;
        }
    }

}

int* smallestK(int* arr, int arrSize, int k, int* returnSize) {
    *returnSize=k;
    if(k==0)
        return NULL; 
    int* retArr=(int*)malloc(sizeof(int)*k);
    for(int i=0;i<k;i++)
    {
        retArr[i]=arr[i];
    }

    for(int i=(k-1-1)/2;i>=0;i--)
    {
        AdjustDown(retArr,k,i);
    }

    for(int i=k;i<arrSize;i++)
    {
        if(arr[i]<retArr[0])
        {
            retArr[0]=arr[i];
            AdjustDown(retArr,k,0);
        }
    }

return retArr;
}